package com.leetcode.algorithm.y22.m06;

/**
 * 123. 买卖股票的最佳时机 III
 * 
 * https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/
 * 
 * @author jie.deng
 *
 */
class Question0123Solution03 {

	/**
	 * 123. 买卖股票的最佳时机 III
	 * https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/ 最多可以完成两笔交易
	 * 
	 * @param prices
	 * @return
	 */
	public int maxProfit(int[] prices) {
		// 数学建模：
		// 某一天买进股票，则当天的收益是 -prices[i]
		// 某一天卖出股票，则当天的收益是 +prices[i]

		// fail-fast
		int len = prices.length;
		if (len == 0) {
			return 0;
		}

		// DP状态定义:
		// 初始化状态
		int buy1 = -prices[0];// 买1次
		int sell1 = 0;// 买1次卖1次
		int buy2 = -prices[0]; // 买1次卖1次，再买1次
		int sell2 = 0;// 买1次卖1次，再买1次再卖1次

		// 决策 a.买进 b.卖出 c.不操作
		// 状态转移方程
		for (int i = 1; i < len; i++) {
			buy1 = Math.max(buy1, -prices[i]);// 之前买入 或者 当天买入
			sell1 = Math.max(sell1, buy1 + prices[i]);// 买1次卖1次
			buy2 = Math.max(buy2, sell1 - prices[i]); // 买1次卖1次，再买1次
			sell2 = Math.max(sell2, buy2 + prices[i]);// 买1次卖1次，再买1次再卖1次
		}

		return sell2;
	}

}